package top.hudk.sort;

import java.util.concurrent.Callable;

/**
 * 作用：
 *
 * @author hudk
 * @date 2020/3/12 9:16
 */
public class Quicksort {

//    public static void main(String[] args) {
//
//        Thread thread ;
////        int n = 100000;
////        int[] arr = new int[n];
////        for(int i=0;i < n; i++){
////            arr[i] = (int)(Math.random() * n)+1;
////        }
////        quickSort(arr);
//        test();
////        int[] arr = new int[]{-1, 2, -3, -8, -10};
////        quickSort(arr,0,arr.length-1);
////        for(int i=0;i < arr.length; i++){
////            System.out.println(arr[i]);
////        }
//
//    }




    public static void quickSort(int[] arr) {
        int[] arr2 = arr.clone();
        long t1 = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long t2 = System.currentTimeMillis();
        quickSort(arr2, 0, arr.length - 1);
        long t3 = System.currentTimeMillis();
        System.out.println(t2 - t1);
        System.out.println(t3 - t2);

    }


    /**
     * 使用递归实现快速排序算法
     * 稳定性：稳定
     * 时间复杂度：O(nlogn)
     * @param nums
     * @param left
     * @param right
     */
    public static void quickSort(int[] nums, int left, int right) {
        int l = left;
        int r = right;
        int m = nums[right];

        while(l < r){
            while(nums[l] < m && l < r){
                l++;
            }
            while(nums[r] > m && l < r){
                r--;
            }
            if (l < r && nums[l] == nums[r]){
                l++;
            }
            else {
                int t = nums[l];
                nums[l] = nums[r];
                nums[r] = t;
            }
        }

        if( l - 1 > left ){
            quickSort(nums, left, l - 1);
        }
        if( r + 1 < right){
            quickSort(nums, r + 1, right);
        }
    }
}
